【题解】 [HNOI2013]切糕 网络流 bzoj3144 | Qiuly's blog!

【题解】 [HNOI2013]切糕 网络流 bzoj3144

Posted on | Edited on | In | Comments:

话说切糕有很多细菌，并且高价，现在不让买了，也不让卖了……..

好吧我们来解决一下这题吧。

额……感觉题意有点不可读，实际上题目就是说给你一个立方体，然后立方体中的每一个点都有一个权值，表示如果要切这个点的话所花费的代价，那么这时需要让你横着切，将这个立方体切成两半，求最小代价。

这就是很明显的最小割了，切成两半使得 $s$ 和 $t$不连通嘛。

于是我们可以考虑这样建边：对于这个立方体，我们建一个虚拟层—第 $0$ 层，对于第 $0$ 层的每一个点，我们用 $s$ 与其相连，这个连接的边是不能被割掉的，所以边权为 $inf$ 。然后对于第 $R$ 层的所有点，我们都将其与 $t$ 相连，同样的道理，边权为 $inf$ 。然后中间的点的话，考虑一个点 $(x,y,z)$ ，我们连一条 $(x−1,y,z)$ 到 $(x,y,z)$ 的边，权值为 $v(x,y,z)$ (即点 $(x,y,z)$ 的权值) 。

这个就是基本的了，如果没有第二个光滑性的限制，直接跑 $Dinic$ 就好了。

但是现在有了这个限制，怎么办呢？

对于一个竖轴，假设这个竖轴的横竖坐标为 $(x,y)$ ，现在在这个竖轴上有一个高度为 $z$ 的点，这个点的坐标显然为 $(x,y,z)$ ，那么现在的情况就是，如果选了 $z$ ，那么相邻竖轴上的 $z−d,z+d$ 都必须选。

于是我们考虑，从 $(x,y,z)$ 向相邻数轴的 $z−d,z+d$ 连一条 $inf$ 的边，这样就可以保证正确性了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define A printf("A")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int dx[5]={0,0,0,-1,1};
const int dy[5]={0,-1,1,0,0};
const int N=8e4+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

int P,Q,R,D,s,t,pointval[42][42][42];
inline int point(int x,int y,int z){return x*P*Q+y*Q+z;}

namespace Dinic{

    std::queue<int> q;
    struct Edge{int nxt,to,val;}G[N<<2];
    int cnt(1),dep[N],head[N];

    inline void add(int u,int v,int w){
        G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
        G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt; 
    }

    inline bool bfs(){
        memset(dep,0,sizeof(dep)); 
        q.push(s);dep[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=head[x];i;i=G[i].nxt){
                int y=G[i].to;
                if(dep[y]||G[i].val<=0)continue;
                dep[y]=dep[x]+1,q.push(y);
            } 
        }return dep[t];
    } 
    inline int dfs(int x,int flow){
        if(x==t||!flow)return flow;
        int used=0,rlow;
        for(int i=head[x];i;i=G[i].nxt){
            int y=G[i].to;
            if(dep[y]==dep[x]+1&&G[i].val){
                used+=(rlow=dfs(y,min(G[i].val,flow-used)));
                G[i].val-=rlow,G[i^1].val+=rlow;
            }
        }if(!used)dep[x]=-1;
        return used;
    }

    inline int dinic(){
        int maxflow=0;
        while(bfs())maxflow+=dfs(s,inf);
        return maxflow;
    }
}

int main(){
    IN(P),IN(Q),IN(R),IN(D);s=0,t=N-1;
    for(int i=1;i<=R;++i)
        for(int j=1;j<=P;++j)
            for(int k=1;k<=Q;++k)
                IN(pointval[i][j][k]);
    for(int j=1;j<=P;++j)
        for(int k=1;k<=Q;++k)
            Dinic::add(s,point(0,j,k),inf);
    for(int i=1;i<=R;++i)  
        for(int j=1;j<=P;++j)
            for(int k=1;k<=Q;++k)
                Dinic::add(point(i-1,j,k),point(i,j,k),pointval[i][j][k]);
    for(int j=1;j<=P;++j)   
        for(int k=1;k<=Q;++k)   
            Dinic::add(point(R,j,k),t,inf);
    for(int i=D;i<=R;++i)  
        for(int j=1;j<=P;++j)
            for(int k=1;k<=Q;++k)  
                for(int l=0;l<5;++l){
                    int tx=dx[l]+j,ty=dy[l]+k;
                    if(tx<1||tx>P||ty<1||ty>Q)continue;
                    Dinic::add(point(i,j,k),point(i-D,tx,ty),inf);
                }
    printf("%d\n",Dinic::dinic());
    return 0;
}

本文标题:【题解】 [HNOI2013]切糕 网络流 bzoj3144

文章作者:Qiuly

发布时间:2019年03月04日 - 00:00

最后更新:2019年03月29日 - 13:52

原始链接:http://qiulyblog.github.io/2019/03/04/[题解]bzoj3144/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。